﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.StateSpaces;
using Algoritmia.Utils;
using Lists = Algoritmia.DataStructures.Lists;
using Sets = Algoritmia.DataStructures.Sets;
using Algoritmia.DataStructures.Maps;

namespace Algoritmia.Problems.ExactCover
{
    namespace DLX
    {
        #region Direction enum

        public enum Direction
        {
            Left, Right, Up, Down
        }

        #endregion


        #region DLX.State class

        public class State : Cell
        {
            public readonly IMap<Cell, int> RowIndex;
            public readonly Sets.ISet<int> Selected;

            public State(IEnumerable<IEnumerable<int>> ones, IEnumerable<int> selected, int n, int m)
                : base(null, null, null, null)
            {
                RowIndex = AlgoritmiaFactory.Maps<Cell, int>.Default;
                Selected = AlgoritmiaFactory.Sets<int>.BuildDefault(selected);
                var list = ones.ToList();
                BuildColumnHeaders(m);
                for (int row = 0; row < n; row++)
                {
                    Cell currentCol = this;
                    Cell first = null;
                    var currentList = list[row].ToList();
                    for (int col = 0; col < m; col++)
                    {
                        currentCol = currentCol.R;
                        if (currentList.Contains(col))
                        {
                            var column = (Column)currentCol;
                            column.S++;
                            var one = new DLX.One(currentCol.U, currentCol, column);
                            RowIndex[one] = row;
                            if (first == null)
                            {
                                first = one;
                            }
                            else
                            {
                                one.L = first.L;
                                one.R = first;
                                one.L.R = first.L = one;
                            }
                            currentCol.U = one.U.D = one;
                        }
                    }
                }

            }

            public override string ToString()
            {
                int j = 0;
                string s = "";
                foreach (Column c in Right())
                {
                    string t = "{" + string.Join(",", c.Down().Select(e => RowIndex[e])) + "}";
                    s += String.Format("c: {0}    {1} \r\n", j, t);
                    j++;
                }
                return s;
            }

            private void BuildColumnHeaders(int m)
            {
                Cell ptr = this;
                for (int i = 0; i < m; i++)
                {
                    ptr.R = new Column();
                    ptr.R.L = ptr;
                    ptr = ptr.R;
                }
                ptr.R = this;
                L = ptr;
            }
        }

        #endregion

        #region Cell class

        public class Cell
        {
            private readonly static Dictionary<Direction, Func<Cell, Cell>> _next;

            public Cell L;
            public Cell R;
            public Cell U;
            public Cell D;

            static Cell()
            {
                _next = new Dictionary<Direction, Func<Cell, Cell>>();
                _next.Add(Direction.Left, cell => cell.L);
                _next.Add(Direction.Right, cell => cell.R);
                _next.Add(Direction.Up, cell => cell.U);
                _next.Add(Direction.Down, cell => cell.D);
            }

            public Cell(Cell l, Cell r, Cell u, Cell d)
            {
                L = l;
                R = r;
                U = u;
                D = d;
            }

            public IEnumerable<Cell> Enumerate(Direction dir)
            {
                if (!_next.ContainsKey(dir))
                {
                    throw new ArgumentException("dir");
                }

                var moveFunction = _next[dir];
                var cell = moveFunction(this);
                while (cell != this)
                {
                    yield return cell;
                    cell = moveFunction(cell);
                }
            }

            public IEnumerable<Cell> Up()
            {
                return Enumerate(Direction.Up);
            }
            public IEnumerable<Cell> Down()
            {
                return Enumerate(Direction.Down);
            }
            public IEnumerable<Cell> Left()
            {
                return Enumerate(Direction.Left);
            }
            public IEnumerable<Cell> Right()
            {
                return Enumerate(Direction.Right);
            }
        }

        #endregion

        #region One class

        public class One : Cell
        {
            public Column Head;

            public One(Cell up = null, Cell down = null, Column head = null)
                : base(null, null, up, down)
            {
                L = this;
                R = this;
                Head = head;
            }

            public void Remove()
            {
                D.U = U;
                U.D = D;
                Head.S--;
            }

            public void Restore()
            {
                U.D = this;
                D.U = this;
                Head.S++;
            }

        }

        #endregion

        #region Column class

        public class Column : Cell
        {
            public int S;

            public Column(Cell left = null, Cell right = null, int s = 0)
                : base(left, right, null, null)
            {
                U = D = this;
                S = s;
            }

            public void Cover()
            {
                var left = L;
                var right = R;
                R.L = left;
                L.R = right;
                foreach (var row in Down())
                {
                    foreach (DLX.One cell in row.Right())
                    {
                        cell.Remove();
                    }
                }
            }

            public void UnCover()
            {
                foreach (var row in Up())
                {
                    foreach (DLX.One cell in row.Left())
                    {
                        cell.Restore();
                    }
                }
                R.L = L.R = this;
            }

            public override string ToString()
            {
                return "Column";
            }
        }
    }
    #endregion

    public class DLX0StateSpace : IReversibleForwardStateSpace<DLX.State, Tuple<DLX.Column, DLX.Cell>>
    {
        private readonly IEnumerable<IEnumerable<int>> _ones;
        private readonly Lists.IList<int> _selected;
        private readonly int _n;
        private readonly int _m;

        public DLX0StateSpace(IEnumerable<IEnumerable<int>> ones, Lists.IList<int> selected = null)
        {
            var onesList = ones.ToList();
            _ones = onesList;
            _selected = selected ?? new int[] { }.ToAlgoritmiaList();
            _n = onesList.Count;
            _m = (from seq in onesList
                  select seq.Max()).Max() + 1;
        }

        #region Implementation of IForwardStateSpace<DLX.State,Tuple<DLX.Column, DLX.Cell>>

        public virtual DLX.State Decide(DLX.State state, Tuple<DLX.Column, DLX.Cell> decision)
        {
            var column = decision.Item1;
            var cellInRow = decision.Item2;
            column.Cover();
            state.Selected.Add(state.RowIndex[cellInRow]);
            foreach (DLX.One one in cellInRow.Right())
            {
                one.Head.Cover();
            }
            return state;
        }

        public virtual IEnumerable<Tuple<DLX.Column, DLX.Cell>> Decisions(DLX.State state)
        {
            var size = _n + 1;
            DLX.Column bestCol = null;
            foreach (DLX.Column column in state.Right())
            {
                if (column.S < size)
                {
                    size = column.S;
                    bestCol = column;
                }
                if (size == 1) break;
            }
            foreach (var cellInRow in bestCol.Down())
            {
                yield return new Tuple<DLX.Column, DLX.Cell>(bestCol, cellInRow);

            }
        }

        public IEnumerable<DLX.State> InitialStates
        {
            get { yield return new DLX.State(_ones, _selected, _n, _m); }
        }

        public bool IsFinal(DLX.State state)
        {
            return state.R == state;
        }

        #endregion

        #region Implementation of IReversibleForwardStateSpace<State,Tuple<DLX.Column, DLX.Cell>>

        public virtual DLX.State Undo(DLX.State state, Tuple<DLX.Column, DLX.Cell> decision)
        {
            var column = decision.Item1;
            var cellInRow = decision.Item2;
            state.Selected.Remove(state.RowIndex[cellInRow]);
            foreach (DLX.Column one in cellInRow.Left())
            {
                one.UnCover();
            }
            column.UnCover();
            return state;
        }

        #endregion
    }
}
